package com.github.zyf.ioaj.algorithm.swarmintelligence;

import com.github.zyf.ioaj.algorithm.Input;
import com.github.zyf.ioaj.algorithm.Output;
import com.github.zyf.ioaj.annotation.internal.Algorithm;
import com.github.zyf.ioaj.annotation.internal.BasicParam;
import com.github.zyf.ioaj.annotation.internal.TempParam;
import com.github.zyf.ioaj.constant.FileType;
import com.github.zyf.ioaj.constant.ParamType;
import com.github.zyf.ioaj.export.*;

/**
 * <h1>Ant Colony Optimization</h1>
 * <p>蚁群算法是一种用来寻找优化路径的概率型算法。</p>
 * <p>默认求解最小值，如果需要求解最大值，将目标函数乘以-1即可，最后得到的值再次乘以-1就是得到的最优值（自变量取值不用乘以-1）</p>
 * <p>需要计算则调用{@link #go()}</p>
 * <p>需要跟踪每次迭代则调用{@link #tracker(String, String, String, FileType)}</p>
 * <p>需要生成报告则调用{@link #report(String, String, String, FileType)}</p>
 * <p>
 * 其基本思想是：单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。
 * 例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。
 * 这是因为蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，
 * 它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，
 * 这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
 * </p>
 * <p>
 * 算法基本步骤为：
 * <ol>
 *     <li>根据信息素浓度计算蚂蚁的转移概率。信息素浓度越大，转移概率越高。</li>
 *     <li>根据转移概率判断蚂蚁的搜索方式（转移方式）。转移概率大于一个转移概率常数时说明此只蚂蚁距离最优解较近，需要进行局部搜索；反之需要进行全局搜索。</li>
 *     <li>更新信息素浓度</li>
 * </ol>
 *
 * <p>
 * 注意：信息素应为非负值，因为需要通过挥发系数来达到挥发（衰减）的目的。
 * 使用调整函数调整信息素取值。调整方式为：如果出现了信息素负值，则调整为每一只蚂蚁的信息素+最小值的相反数；否则什么也不用做。
 * </p>
 *
 * @author zyf
 */
@Algorithm
public class ACO extends SwarmIntelligenceAlgorithm {


    /**
     * 信息素挥发系数
     */
    @BasicParam(type = ParamType.DOUBLE, desc = "信息素挥发系数")
    private double rho;

    /**
     * 转移概率常数
     */
    @BasicParam(type = ParamType.DOUBLE, desc = "转移概率常数")
    private double P0;

    /**
     * 蚂蚁的位置
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_2,desc = "蚂蚁的位置")
    private double[][] ant;

    /**
     * 蚂蚁的信息素浓度
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_1,desc = "蚂蚁的信息素浓度")
    private double[] pheromone;

    /**
     * 每只蚂蚁的转移概率
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_1,desc = "每只蚂蚁的转移概率")
    private double[] p;

    /**
     * 当前群体最优解
     */
    @TempParam(type = ParamType.DOUBLE_ARRAY_1,desc = "当前群体最优解")
    private double[] x;

    /* 初始化部分 */

    /**
     * 抽象算法构造函数，需要提供输入量，即提前初始化好{@link Input}对象
     *
     * @param input {@link Input}
     */
    public ACO(Input input) {
        super(input);
        init();
    }

    private void init() {
        this.rho = 0.9;
        this.P0 = 0.8;
        this.p = new double[getN()];

        initPheromone();
        initAnt();
        initX();
    }

    private void initPheromone() {
        pheromone = new double[getN()];
        int i;
        for (i = 0; i < getN(); i++) {
            pheromone[i] = 0.0;
        }
    }

    private void initAnt() {
        ant = new double[getN()][getInput().getVarNum()];
        int i, j;
        for (i = 0; i < getN(); i++) {
            for (j = 0; j < getInput().getVarNum(); j++) {
                ant[i][j] = getInput().getLb()[j] + Math.random() * (getInput().getUb()[j] - getInput().getLb()[j]);
            }
            pheromone[i] = getInput().getFunction().apply(ant[i]);
        }
        x = ant[0].clone();
    }

    private void initX() {
        int i;
        for (i = 0; i < getN(); i++) {
            if (pheromone[i] < getInput().getFunction().apply(x)) {
                x = ant[i].clone();
            }
        }
    }

    /* 计算部分 */

    /**
     * 为保证信息素正常衰减，调整所有值非负
     *
     * @param pheromone_val 待调整的信息素数组
     */
    private void adjust(double[] pheromone_val) {
        int i;
        double min_val = pheromone_val[0];
        for (i = 0; i < getN(); i++) {
            min_val = Math.min(min_val, pheromone_val[i]);
        }
        if (min_val < 0) {
            min_val = -min_val;
            for (i = 0; i < getN(); i++) {
                pheromone_val[i] += min_val;
            }
        }
    }

    /**
     * 每次迭代时扫描一遍
     *
     * @param t 第几次迭代
     */
    public void scan(int t) {
        int i, j;
        // 局部搜索步长，随迭代次数增加步长逐渐减小
        double step = 1.0 / t;
        // 设置每只蚂蚁的转移概率，信息素越多， 转移概率越大
        double phero_max = pheromone[0];
        for (i = 0; i < getN(); i++) {
            phero_max = Math.max(phero_max, pheromone[i]);
        }
        for (i = 0; i < getN(); i++) {
            p[i] = pheromone[i] / phero_max;
        }
        double[] new_pheromone = new double[getN()];

        for (i = 0; i < getN(); i++) {
            for (j = 0; j < getInput().getVarNum(); j++) {
                if (p[i] >= P0) {
                    // 局部搜索保证正负均衡
                    ant[i][j] += (Math.random() - 0.5) * step;
                } else {
                    // 全局搜索
                    ant[i][j] += (Math.random() - 0.5) * (getInput().getUb()[j] - getInput().getLb()[j]);
                }
                // 调整自变量值避免越界
                if (ant[i][j] < getInput().getLb()[j]) ant[i][j] = getInput().getLb()[j];
                if (ant[i][j] > getInput().getUb()[j]) ant[i][j] = getInput().getUb()[j];
            }
            // 更新最优位置
            if (getInput().getFunction().apply(ant[i]) < getInput().getFunction().apply(x)) x = ant[i].clone();
            new_pheromone[i] = getInput().getFunction().apply(ant[i]);
        }
        adjust(new_pheromone);
        for (i = 0; i < getN(); i++) {
            pheromone[i] = (1 - rho) * pheromone[i] + new_pheromone[i];
        }
    }

    /**
     * 生成最优解
     */
    private void generateOptimization() {
        // 获取最优值
        double optimalOutput = getInput().getFunction().apply(x);
        // 获取最优值时自变量取值
        double[] optimalInput = x;
        setOutput(new Output(optimalOutput, optimalInput));
    }

    /**
     * 运行并计算结果
     */
    @Override
    public void go() {
        adjust(pheromone);
        int t;
        for (t = 0; t < getIter(); t++) {
            scan(t);
        }
        generateOptimization();
    }

    /**
     * 运行并计算结果（按迭代逐步跟踪），如果目的是计算出结果，请使用{@link #go()}
     *
     * @param author   作者
     * @param message  备注
     * @param title    标题
     * @param fileType 文件类型 {@link FileType}
     * @return {@link Tracker}
     */
    @Override
    public Tracker tracker(String author, String message, String title, FileType fileType) {
        int t;
        Tracker tracker = new Tracker(this, author, message, title, fileType);
        tracker.startTracker();
        for (t = 0; t < getIter(); t++) {
            scan(t);
            tracker.trackOne(t + 1);
        }
        generateOptimization();
        tracker.endTracker();
        return tracker;
    }

    /**
     * 生成报告
     *
     * @param author   作者
     * @param message  备注
     * @param title    标题
     * @param fileType 文件类型 {@link FileType}
     * @return {@link Report}
     */
    @Override
    public Report report(String author, String message, String title, FileType fileType) {
        return new Report(this, author, message, title, fileType);
    }

    /* Getter/Setter 部分 */

    public double getRho() {
        return rho;
    }

    public void setRho(double rho) {
        this.rho = rho;
    }

    public double getP0() {
        return P0;
    }

    public void setP0(double p0) {
        P0 = p0;
    }

    /* Getter部分 */
    public double[][] getAnt() {
        return ant;
    }

    public double[] getPheromone() {
        return pheromone;
    }

    public double[] getP() {
        return p;
    }

    public double[] getX() {
        return x;
    }
}
